This invention relates to communication networks and, more particularly, to a method for testing the integrity of packet data using a single data check field which supports tests for changes in packet contents and ordering following a switching or transfer operation.
Very high rate data communication networks are becoming increasingly common, due in part to the deployment of optical fibers capable of transmitting data at extremely high rates. Switching of fixed-length packets (cells) at network nodes is recognized as one of the best ways to take advantage of the potential performance offered by such fibers. Nodes or systems on the network are connected via one or more switches which route the cells to their various destinations. The term xe2x80x9cswitchxe2x80x9d is ordinarily used to refer to a system which includes input and output adapters with buffering capabilities and a switching fabric which performs the actual switching of cells from an input adapter to the appropriate output adapter.
Switches are interconnected through inbound and outbound communication links. Links, while logically separate, are paired such that one inbound and one outbound connection form a full-duplex link tied to a switch port. Cells are received from an inbound link by the switch and retransmitted on one of the outbound links according to the routing rules of the protocol in use within the network; for instance, Asynchronous Transfer Mode (ATM).
The core of the switching process, as it is defined for ATM, is as follows. A header in a cell received on an inbound link is examined to identify the outbound link on which it must be forwarded. The contents of the header are typically changed in the switch to new values needed for switching of the cell at the next system on its path; that is, the switch at the remote end of the outbound link. The cell is transmitted towards its destination on the selected outbound link. During this process the system is constrained to deliver cells to the appropriate output port for the selected outbound link in the same sequence as the cells arrive at the switch.
The same physical link normally carries multiple logical or virtual connections between switches. The switching process described above is applied for each virtual connection carried on the same physical link.
For the sake of simplicity and to accommodate different applications, the route of a cell through the switching fabric is preferably specified by a routing vector or tag prefixed to the cell itself. The routing tag is added at the input adapter processing the cell and is used by the switching fabric to select the output adapter or adapters (in case of multicasting) to which the cell is to be directed. To guarantee cell data integrity during a switching operation, an input adapter conventionally generates a check field value based only on the cell contents and appends the check field to the cell. The output port adapter receiving the cell employs the check field and known error detection techniques to verify that the contents of the cell have not changed during the switching operation. Normally, the check field is generated using a standard Cyclic Redundancy Check (CRC) algorithm.
Each output adapter receiving the switched cell removes the routing tag and the check field before the cell is transmitted toward the next switch on a virtual connection.
More information on ATM technology is available in xe2x80x9cAsynchronous Transfer Mode (ATM), Technical Overviewxe2x80x9d a publication by the IBM International Technical Support Organization, reference SG24-4625, dated October 1995.
The process described above can be used to detect permanent and/or intermittent hardware or software problems in a switching fabric, permitting the switch to be isolated for maintenance and repair. In redundant systems, a failing switch may be automatically deactivated with switching operations being transferred to a parallel active switch to provide an interruption-free mode of operation. Interruption-free or fail-safe operation is often a requirement for communication networks that are assumed to operate 24 hours a day.
In most communication networks, the amount of data traffic extant at any particular point in the network can increase abruptly as the number of sources providing data increases and/or as existing sources increase the amount of data they are supplying. Consequently, congestion may occur almost anywhere in a network. The response of a switch to congestion is dependent on its design. However, a common response is that one or more cells are dropped or discarded because internal queues or buffers overflow. Also, because of design flaws in the hardware or software which controls a switch, cells may get out of sequence during switching.
The fact that one or more cells have been dropped or are out of sequence is not detected by normal error checking using a conventional CRC check field because the check field value is generated solely as a function of the contents of the particular cell to which it is appended. Missing or out-of-sequence cells typically must be detected by higher-layer processes performed only at the endpoints of a source-to-destination path. Known higher-layer processes do not locate the source of a failure which can occur at any of the several nodes along the source-to-destination path.
The traditional way of handling the detection of dropped or out-of-sequence cells is to include a sequence number in every cell. The obvious drawback of this method is that an extra field must be allocated in the cell to transport the sequence number information. An example of the use of an extra field is the Adaptation Layer 1 of ATM (also described in the xe2x80x9cTechnical Overviewxe2x80x9d previously mentioned) which deals with the transport of constant-bit-rate traffic such as digitized voice. The specification for Adaptation Layer 1 solves the problem of having to insert a sequence number into each cells by borrowing a byte from the cell data payload. This necessarily reduces the available data payload from its regular 48-byte format to a non-standard 47-byte useful payload, which complicates data manipulation in the temporary buffers and queues generally found in switch adapters.
In the general case, data originally formatted using protocols than ATM may need to be handled in a cell-based communication network. As a consequence, cells being processed in a switch may be the result of the segmentation of messages received by the input adapter. In such cases it is important to preserve cell sequencing so as to permit a proper re-assembling of messages in the switch""s output adapter or at a final destination.
It is a first object of the invention to provide a method for generating a data check field to be appended to a packet being processed in a network, the check field being usable for detecting alterations in packet contents as packet sequencing problems. It is a second object of the invention to achieve this dual detection capability with a minimum check field length while maintaining all detection capabilities of a CRC check field.
The invention can be implemented as a method for generating a check field to be appended to packets to be processed in a data communications network. The method comprises the following steps. A regular CRC calculation is performed for the packet fields to be protected, yielding an initial value for a check field. A packet connection counter is incremented for each new processed packet. The number of output stages in the counter is less than or equal to the degree of the generator polynomial used to compute the CRC. The initial value of the check field is modified by exclusively OR""ing the current counter outputs with the initial (CRC) value, producing a final value for the check field. The final value of the check field is appended to the packet.
A check field generated in the manner described above can be tested to in an output adapter to test for changes in the protected fields and/or packet sequencing problems resulting from switching or other packet transfer operations. The test method comprises the steps of performing a CRC calculation for the protected fields of the packet, including the appended check field, yielding a partial check result. An outbound packet connection counter is incremented for each new outbound packet. on the selected connection. Like the counter used for the check field generation process, the outbound packet counter has a number of stages less than or equal to the degree of the polynomial used to compute the CRC. The CRC calculation or partial check result is compared to the current count, which may or may not result in a non-null value. A null value indicates that the cell contents did not change during processing through the switching fabric and that all packets have been received in the right sequence. A non-null value indicates an error of some kind.
The present invention converts a regular CRC field into a composite check field which permits detection of changes within the protected fields. The composite check field additionally supports detection of packet sequencing problems when the calculations are performed on successive packets.